package com.awesome.javademo.algorithm.solution;

import android.text.TextUtils;

import com.awesome.javademo.algorithm.bean.Automaton;
import com.awesome.common.util.log.ShowLogUtil;

import java.util.HashMap;
import java.util.Map;
import java.util.regex.Pattern;

/**
 * Author: JfangZ
 * Email: zhangjingfang@jeejio.com
 * Date: 2021/3/15 13:51
 * Description:
 */
public class SolutionString {

    /**
     * 题目：反转字符串
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
     * 输入：s = ["h","e","l","l","o"]
     * 输出：["o","l","l","e","h"]
     * 输入：s = ["H","a","n","n","a","h"]
     * 输出：["h","a","n","n","a","H"]
     * 提示：
     * 1 <= s.length <= 105
     * s[i] 都是 ASCII 码表中的可打印字符
     *
     * 双指针
     * 时间复杂度O(n)
     * 空间复杂度O(1)
     */
    public static char[] reverseString(char[] s) {
        int length = s.length;
        for (int i = 0; i < length / 2; i++) {
            char temp = s[i];
            s[i] = s[length - 1 - i];
            s[length - 1 - i] = temp;
        }
        return s;
    }

    public static char[] getChars(){
        char[] chars = {'a','b','c','1','2'};
        return chars;
    }

    public static void printChars(char[] chars){
        for (int i = 0; i <chars.length; i++) {
            ShowLogUtil.info(chars[i]);
        }
    }

    /**
     * 题目：整数反转
     * 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
     * 如果反转后整数超过 32 位的有符号整数的范围[−231, 231− 1] ，就返回 0。
     * 假设环境不允许存储 64 位整数（有符号或无符号）。
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
     * 输入：x = 123
     * 输出：321
     * 输入：x = -123
     * 输出：-321
     * 输入：x = 120
     * 输出：21
     * 输入：x = 0
     * 输出：0
     * 提示：
     * -231 <= x <= 231 - 1
     *
     * 时间复杂度O(n)
     * 空间复杂度O(1)
     * 弹出和推入数组&移除前进行检查？
     */
    public static int reverse(int x) {
        boolean isNegative = (x < 0);
        long absX = x;
        absX = Math.abs(absX);
        char[] chars = String.valueOf(absX).toCharArray();
        char[] reverseChars = reverseString(chars);
        String reverseStr = String.valueOf(reverseChars);
        long reverseLong = Long.parseLong(reverseStr);
        if (isNegative) reverseLong = -1 * reverseLong;
        if (reverseLong > Integer.MAX_VALUE || reverseLong < Integer.MIN_VALUE) {
            return 0;
        } else {
            return (int) reverseLong;
        }
    }

    public static int getInt() {
//        return 123;
//        return -123;
//        return 120;
//        return 0;
//        return -2147483648;
//        return 2147483647;
//        return -2147483641;
        return 2147483641;
    }

    // 字符串中的第一个唯一字符
    // 使用哈希表存储频数
    // 时间复杂度O(n)
    // 空间复杂度O(∣Σ∣)
    // 使用哈希表存储索引
    // 时间复杂度O(n)
    // 空间复杂度O(∣Σ∣)
    // 队列?
    // SolutionString.firstUniqChar("loveleetcode");
    public static int firstUniqChar(String s) {
//        Map<Character, Integer> hashMap = new HashMap<>();
//        for (int i = 0; i < s.length(); i++) {
//            hashMap.put(s.charAt(i), hashMap.getOrDefault(s.charAt(i), 0) + 1);
//        }
//        for (int i = 0; i < s.length(); i++) {
//            if (hashMap.get(s.charAt(i)) == 1) return i;
//
//        }
//        return -1;
        Map<Character, Integer> hashMap = new HashMap<>();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (hashMap.containsKey(ch)) {
                hashMap.put(ch, -1);
            } else {
                hashMap.put(ch, i);
            }
        }
        int first = -1;
        for (Map.Entry<Character, Integer> entry : hashMap.entrySet()) {
            Integer value = entry.getValue();
            if (value != -1 && value < length) {
                first = value;
            }
        }
        return first;


//        Map<Character, Integer> position = new HashMap<Character, Integer>();
//        int n = s.length();
//        for (int i = 0; i < n; ++i) {
//            char ch = s.charAt(i);
//            if (position.containsKey(ch)) {
//                position.put(ch, -1);
//            } else {
//                position.put(ch, i);
//            }
//        }
//        int first = n;
//        for (Map.Entry<Character, Integer> entry : position.entrySet()) {
//            int pos = entry.getValue();
//            if (pos != -1 && pos < first) {
//                first = pos;
//            }
//        }
//        if (first == n) {
//            first = -1;
//        }
//        return first;
    }

    // 有效的字母异位词
    // 排序
    // 数组
    // 时间复杂度O(m+n)
    // 空间复杂度O(S)
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] letter = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            letter[ch - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            letter[ch - 'a']--;
            if (letter[ch - 'a'] < 0) return false;
        }
        return true;
    }

    // 验证回文串
    // 筛选 + 判断
    // 时间复杂度O(∣s|)
    // 空间复杂度O(∣s|)
    // 在原字符串上直接判断
    // 时间复杂度O(∣s|)
    // 空间复杂度O(1)
    // SolutionString.isPalindrome(".,")
    public static boolean isPalindrome(String s) {
//        StringBuffer sb = new StringBuffer();
//        for (int i = 0; i < s.length(); i++) {
//            if (Character.isLetterOrDigit(s.charAt(i)))
//                sb.append(s.charAt(i));
//        }
//        String newStr = sb.toString();
//        int newStrLength = sb.toString().length();
//        for (int i = 0; i < newStrLength / 2; i++) {
//            if (newStr.charAt(i) != newStr.charAt(newStrLength - i)) return false;
//        }
//        return true;
        if (s == null) return false;
        int length = s.length();
        int left = 0;
        int right = length - 1;
        while (left < right) {
            while (!Character.isLetterOrDigit(s.charAt(left))) {
                if (left == right) return true;
                if (left > right - 1) break;
                left++;
            }
            while (!Character.isLetterOrDigit(s.charAt(right))) {
                right--;
                if (right < left + 1) break;
            }
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))
                return false;
            left++;
            right--;
        }
        return true;
    }

    // 实现strStr()
    public static int strStr(String haystack, String needle) {
        if (haystack == null || needle == null)
            return -1;
        if (needle.length() == 0)
            return 0;
        char firstLitter = needle.charAt(0);
        int haystackLength = haystack.length();
        int needleLength = needle.length();
        for (int i = 0; i < haystack.length(); i++) {
            if (firstLitter == haystack.charAt(i)) {
                if (haystackLength >= i + needleLength) {
                    if (haystack.substring(i, i + needleLength).equals(needle))
                        return i;
                } else {
                    return -1;
                }
            }
        }
        return -1;
    }

    // 外观数列
//    public static String countAndSay(int n) {
//    }

    // 最长公共前缀
    // SolutionString.longestCommonPrefix(new String[]{"dog","racecar","car"});
    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 0; i < strs.length; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0)
                return "";
        }
        return prefix;
    }


    public static String longestCommonPrefix(String s1, String s2) {
        int length = Math.min(s1.length(), s2.length());
        int index = 0;
        while (length > 0 && (s1.charAt(index) == s2.charAt(index))) {
            index++;
            length--;
        }
        return s1.substring(0, index);
    }

    //字符串转整数

    public static int atoi(String str) {
        Automaton automaton = new Automaton();
        int length = str.length();
        for (int i = 0; i < length; ++i) {
            automaton.get(str.charAt(i));
        }
        return (int) (automaton.sign * automaton.ans);
    }


    /**
     * 题目：字符串转换整数 (atoi)
     * 请你来实现一个myAtoi(string s)函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
     * 函数myAtoi(string s) 的算法如下：
     * 读入字符串并丢弃无用的前导空格
     * 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。
     * 如果两者都不存在，则假定结果为正。
     * 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
     * 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。
     * 必要时更改符号（从步骤 2 开始）。
     * 如果整数数超过 32 位有符号整数范围 [−231, 231− 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，
     * 小于 −231 的整数应该被固定为 −231 ，大于 231− 1 的整数应该被固定为 231− 1 。
     * 返回整数作为最终结果。
     * 注意：
     * 本题中的空白字符只包括空格字符 ' ' 。
     * 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
     * 输入：s = "42"
     * 输出：42
     * 解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
     * 第 1 步："42"（当前没有读入字符，因为没有前导空格）
     *          ^
     * 第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
     *          ^
     * 第 3 步："42"（读入 "42"）
     *            ^
     * 解析得到整数 42 。
     * 由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。
     *
     * 输入：s = "   -42"
     * 输出：-42
     * 解释：
     * 第 1 步："   -42"（读入前导空格，但忽视掉）
     *             ^
     * 第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
     *              ^
     * 第 3 步："   -42"（读入 "42"）
     *                ^
     * 解析得到整数 -42 。
     * 由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
     *
     * 输入：s = "4193 with words"
     * 输出：4193
     * 解释：
     * 第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
     *          ^
     * 第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
     *          ^
     * 第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
     *              ^
     * 解析得到整数 4193 。
     * 由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。
     *
     * 输入：s = "words and 987"
     * 输出：0
     * 解释：
     * 第 1 步："words and 987"（当前没有读入字符，因为没有前导空格）
     *          ^
     * 第 2 步："words and 987"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
     *          ^
     * 第 3 步："words and 987"（由于当前字符 'w' 不是一个数字，所以读入停止）
     *          ^
     * 解析得到整数 0 ，因为没有读入任何数字。
     * 由于 0 在范围 [-231, 231 - 1] 内，最终结果为 0 。
     *
     * 输入：s = "-91283472332"
     * 输出：-2147483648
     * 解释：
     * 第 1 步："-91283472332"（当前没有读入字符，因为没有前导空格）
     *          ^
     * 第 2 步："-91283472332"（读入 '-' 字符，所以结果应该是负数）
     *           ^
     * 第 3 步："-91283472332"（读入 "91283472332"）
     *                      ^
     * 解析得到整数 -91283472332 。
     * 由于 -91283472332 小于范围 [-231, 231 - 1] 的下界，最终结果被截断为 -231 = -2147483648 。
     */

    public static int myAtoi(String str) {
        if (TextUtils.isEmpty(str)) return 0;
        String regex = "[0-9]";
        StringBuilder stringBuilder = new StringBuilder();
        long l = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (Pattern.matches(regex, c + "")) {
                stringBuilder.append(c);
            } else if (c == ' ') {

            } else if ((c == '-' || c == '+') && stringBuilder.length() == 0) {
                stringBuilder.append(c);
            } else {
                break;
            }
        }
        if (stringBuilder.length() == 0) return 0;
        if (stringBuilder.charAt(0) == '-' || stringBuilder.charAt(0) == '+') {
            if (stringBuilder.length() > 11) {
                l = Long.parseLong(stringBuilder.substring(0, 11));
            } else {
                l = Long.parseLong(stringBuilder.toString());
            }
        } else {
            if (stringBuilder.length() > 10) {
                l = Long.parseLong(stringBuilder.substring(0, 10));
            } else {
                l = Long.parseLong(stringBuilder.toString());
            }
        }
        if (l < -2147483648) {
            l = -2147483648;
        }
        if (l > 2147483647) {
            l = 2147483647;
        }
        return (int) l;
    }
}
